#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int R,n;
typedef struct node{
	int l,t,w,h;
}node;
int sum=0;
node jx[10005];
bool cmp(node a,node b){
	return a.l+a.w<b.l+b.w;
}

int calS(int m){
	int s=0;
	for(int i=1;i<=n;i++){
		if(jx[i].l+jx[i].w<=m){
			s+=(jx[i].w*jx[i].h);
		}else{
			if(m-jx[i].l>0)
				s+=(jx[i].h*(m-jx[i].l));
			else
				break;
			
		}
	}
	return s;
}

bool check(int m){
	int s=calS(m);
	if(s>=(sum-s)) return true;
	else return false;
}
int main(){
	cin>>R>>n;
	for(int i=1;i<=n;i++){
		cin>>jx[i].l>>jx[i].t>>jx[i].w>>jx[i].h;
		sum+=jx[i].w*jx[i].h;
	}
	sort(jx+1,jx+1+n,cmp);
	int l=1,r=R;
	int ans,mid;
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	int s=calS(ans);
	for(int i=ans+1;i<=R;i++){
		if(s==calS(i)){
			ans=i;
			continue;
			
		}else{
			break;
		}
	}
	
	cout<<ans;
	return 0;
}
